package com.shm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 71. 简化路径
 * 以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
 *
 * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
 *
 * 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
 *
 *
 *
 * 示例 1：
 *
 * 输入："/home/"
 * 输出："/home"
 * 解释：注意，最后一个目录名后面没有斜杠。
 * 示例 2：
 *
 * 输入："/../"
 * 输出："/"
 * 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
 * 示例 3：
 *
 * 输入："/home//foo/"
 * 输出："/home/foo"
 * 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
 * 示例 4：
 *
 * 输入："/a/./b/../../c/"
 * 输出："/c"
 * 示例 5：
 *
 * 输入："/a/../../b/../c//.//"
 * 输出："/c"
 * 示例 6：
 *
 * 输入："/a//b////c/d//././/.."
 * 输出："/a/b/c"
 * @author SHM
 */
public class SimplifyPath {
    /**
     * 这道题要求我们将一个 Unix 风格的绝对路径转换为规范路径（这里忽略题目中的大段描述）。输入是一个字符串，在这个字符串里有一些斜杠，这些斜杠表示 目录 或者 操作 的分隔符。
     *
     * 具体来说：
     *
     * 如果是英文字母，就表示一个 目录。
     * 如果是一个点或者两个点，表示的是 操作。其中一个点 . 表示停留在当前目录，两个点 .. 表示返回上一级目录。
     * 题意分析：从题目的文字说明和 33 个示例中我们知道（看示例理解题意很重要）：
     *
     * 规范的路径的 结尾 不能有斜杠；
     * 出现两个小圆点 .. 的时候，它前面的那个表示目的字符串可以当做不存在。即：简化的目的是 去掉多余的斜杠和目录 。
     * 我们再分析一下：题目为什么需要我们简化它呢？原因是有 .. 表示返回上一级目录。例如：/a/b/../.. 这个表示路径的字符串，表示先进入目录 a 再进入目录 b ，然后遇到两个.. 回到它的父目录，也就是回到了目录 a ，然后又遇到两个.. 回到它的父目录，也就是回到了根目录 / ，那么这个路径就被简化为一个斜杠 /。题目要我们返回这个斜杠。
     *
     *
     *
     * 另外我们注意到示例 3：有两个斜杠连在一起的情况，此时认为这两个斜杠中间是一个空字符，空字符等价于一个点 . ，即什么都不做。
     *
     * 算法设计：需要先对字符串根据斜杠 /进行分割，得到一个字符串数组。这个字符串数组的字符串可能有以下几种：.、..、''、和表示目录的字母。
     *
     * 从左向右遍历字符串数组，如果遇到字母就直接入栈，如果遇到一个点 . 或者空格的时候，就什么都不做。如果遇到两个点 .. ，就将栈顶元素从栈中弹出。
     *
     * 从上面的例子我们还看出，需要知道上级目录和上上级目录。因此，记录上级目录、上上级目录的变量就是一个列表对象。这就是我们之前说的 栈和队列都是缓存数据的线性容器，我们需要把读到的数据暂时存起来，栈和队列就是两种常见的存储数据的容器。
     *
     * 栈顶元素表示了已读出的目录结构中，最先需要被化简（移除）的那个目录结构。
     *
     * 我们看一眼题目中给出的示例 2 和示例 5："/a/../../b/../c//.//"，先读到目录 a，然后做了两次回退操作，第 11 次回退的时候，就退到了根目录，事实上已经不能再回退了，此时 .. 这个操作无效。因此在编码的时候，需要注意：只有在栈顶元素非空的时候，我们才能进行弹栈的操作。
     *
     * 复杂度分析：
     *
     * 时间复杂度：O(N)O(N)，这里 NN 是数组的长度，最坏情况下，每个字符串进栈一次，出栈一次，表示操作的字符串还不用进栈出栈，因此时间复杂度是线性的；
     * 空间复杂度：O(N)O(N) ，最坏情况下，这个路径字符串本身就是化简过的，栈中就要存字符串长度这么多的字符串（近似，不包括那些斜杠）。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/5wkuf7/
     * @param path
     * @return
     */
    public String simplifyPath(String path) {
        String[] ss = path.split("/");
        Deque<String> stack = new LinkedList<>();
        for(String s:ss){
            if("".equals(s)||".".equals(s)){
                continue;
            }
            if("..".equals(s)){
                // 注意：只有栈非空的时候才能弹出，注意下面 continue; 的作用
                if(!stack.isEmpty()){
                    stack.removeLast();
                }
                continue;
            }
            stack.addLast(s);
        }
        StringBuilder sb = new StringBuilder();

//        while(!stack.isEmpty()){
//            sb.insert(0,stack.removeLast());
//            sb.insert(0,"/");
//        }
//        if(sb.length()==0){
//            sb.insert(0,"/");
//        }

        if(stack.isEmpty()){
            sb.append("/");
        }else{
            while (!stack.isEmpty()){
                sb.append("/");
                sb.append(stack.pollFirst());
            }
        }

        return sb.toString();
    }
}
